﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace LemonKnapsack01
{

    public class Program
    {
        static void Main()
        {
            // 测试数据
            int capacity = 10;
            int[] weights = { 2, 3, 4, 5 };
            int[] values = { 3, 4, 5, 6 };

            Console.WriteLine("=== 0-1背包问题解决方案 ===");
            Console.WriteLine($"背包容量: {capacity}");
            Console.WriteLine($"物品重量: [{string.Join(", ", weights)}]");
            Console.WriteLine($"物品价值: [{string.Join(", ", values)}]");
            Console.WriteLine();

            // 基础版本
            int maxValue = Knapsack01.Solve(capacity, weights, values);
            Console.WriteLine($"基础版本 - 最大价值: {maxValue}");

            // 空间优化版本
            int maxValueOpt = Knapsack01Optimized.SolveOptimized(capacity, weights, values);
            Console.WriteLine($"优化版本 - 最大价值: {maxValueOpt}");

            // 显示DP表（基础版本）
            DisplayDPTable(capacity, weights, values);
        }

        static void DisplayDPTable(int capacity, int[] weights, int[] values)
        {
            int n = weights.Length;
            int[,] dp = new int[n + 1, capacity + 1];

            // 计算DP表
            for (int i = 0; i <= n; i++)
            {
                for (int j = 0; j <= capacity; j++)
                {
                    if (i == 0 || j == 0)
                    {
                        dp[i, j] = 0;
                    }
                    else if (j >= weights[i - 1])
                    {
                        dp[i, j] = Math.Max(
                            dp[i - 1, j],
                            dp[i - 1, j - weights[i - 1]] + values[i - 1]
                        );
                    }
                    else
                    {
                        dp[i, j] = dp[i - 1, j];
                    }
                }
            }

            Console.WriteLine("\nDP表:");
            Console.Write("i\\j\t");
            for (int j = 0; j <= capacity; j++)
            {
                Console.Write($"{j}\t");
            }
            Console.WriteLine();

            for (int i = 0; i <= n; i++)
            {
                Console.Write($"{i}\t");
                for (int j = 0; j <= capacity; j++)
                {
                    Console.Write($"{dp[i, j]}\t");
                }
                Console.WriteLine();
            }

            // 找出选择的物品
            Knapsack01.FindSelectedItems(capacity, weights, values, dp);
        }
    }
}
